Selection sort & Insertion sort

selection sort
가장 작은 것을 선택해서 앞으로 보내는 정렬 기법.
가장 작은 것을 선택하는데에 N번 앞으로 보내는 데에 N번의 연산으로 O(N^2)의 시간 복잡도를 가짐
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<limits.h>
#define SIZE 1000
int a[SIZE];
int swap(int *a, int *b){
int temp= *a;
*a=*b;
*b=temp;
}
int main(void){
int n, min, index;
scanf("%d", &n);
for(int i=0;i<n;i++)scanf("%d", &a[i]);
for(int i=0;i<n;i++){
min=INT_MAX;
for(int j=i;j<n;j++){
if(min>a[j]){
min=a[j];
index=j;
}
}
swap(&a[i], &a[index]);
}
for(int i=0;i<n;i++)printf("%d ", a[i]);
system("pause");
return 0;
}
Insertion sort
각 숫자를 적절한 위치에 삽입하는 정렬 기법
들어갈 위치를 선택하는데에 N번, 선택하는 횟수로 N번이므로 O(N^2)의 시간 복잡도를 가진다.

선택정렬과 동일한 시간복잡도를 가지지만 일반적으로 선택정렬보다 조금 더 빠름
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<limits.h>
#define SIZE 1000
int a[SIZE];
int swap(int *a, int *b){
int temp= *a;
*a=*b;
*b=temp;
}
int main(void){
int n;
scaf("%d", &n);
for(int i=0;i<n;i++)scanf("%d",&a[i]);
for(int i=0;i<n-1;i++){
int j=i;
while(j>=0 && a[j]>a[j+1]){
swap(&a[j], &a[j+1]);
j--;
}
}
for(int i=0;i<n;i++)printf("%d ", a[i]);
system("pause");
return 0;
}